\bigskip
\bigskip
{\magonebf 5.8 Two dimensional node arrays  (node\_matrix)}


An instance $M$ of the data type $node\_matrix$  is 
a partial mapping from the set of node pairs $V\times V$
of a graph to a set of variables of a data type $E$, called the element type 
of $M$. The domain $I$ of $M$ is called the index set of $M$. $M$ is said to 
be valid for all node pairs in $I$. A node matrix can also be viewed as a 
node array with element type $node\_array(E)$ ($node\_array(node\_array(E))$). 


\bigskip
{\bf 1. Declaration of a node matrix type}

\decl node\_matrix E 

introduces a new data type with name \name\ consisting of all 
node matrices with element type $E$.


\bigskip
{\bf 2. Creation of a node\_matrix}


a) \create M {}

b) \create M (G)

c) \create M (G,x)

creates an instance $M$ of type \name. Variant a) initializes the index set 
of $M$ to the empty set, Variants b) and c) initialize the index set of $A$ 
to be the set of all node pairs of graph $G$, i.e., $M$ is made valid for all 
pairs in $V \times V$ where $V$ is the set of nodes currently contained in $G$. 
Variant c) in addition initializes  $M(v,w)$ with $x$ for all nodes $v,w \in V$.


\bigskip
{\bf 3. \operations }
\medskip
\+\op void  init {graph\ G}         
                             {sets the index set of $M$ to $V\times V$, where }
\+\nop                       {$V$ is the set of all nodes of $G$ }
\smallskip
\+\op void  init {graph\ G,\ E\ x}    
                            {sets the index set of $M$ to $V\times V$, where }
\+\nop                      {$V$ is the set of all nodes of $G$ and initializes}
\+\nop                      {$M(v,w)$ to $x$ for all $v,w \in V$.}
\smallskip
\+\opf E\&  {node\ v,\ node\ w}
                            {returns the variable $M(v,w)$.}
\+\nop                      {\precond $M$ must be valid for $v$ and $w$.}
\smallskip
\+&$node\_array(E)\&$ $M[v]$ &&returns the node\_array  $M(v).$\cr

\bigskip
{\bf 4. Implementation}

Node matrices for a graph $G$ are implemented by vectors of node arrays and an 
internal numbering of the nodes of $G$. The access operation 
takes constant time, the init operation takes time $O(n^2)$, where $n$ is the 
number of nodes currently contained in $G$. The space requirement is $O(n^2)$.
Note that a node matrix is only valid for the nodes contained in $G$ at the 
moment of the matrix declaration or initialization ($init$). Access operations 
for later added nodes are not allowed.


